package likou;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/09 09:26
 */
public class _973 {
    public static void main(String[] args) {
        System.out.println(kClosest(new int[][]{{3,3},{5,-1},{-2,4}},2));
    }
    public static int[][] kClosest(int[][] points, int K) {
        int [][] daan = new int[K][2];
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                long one = o2[0]*o2[0]+o2[1]*o2[1];
                long two = o1[0]*o1[0]+o1[1]*o1[1];
                System.out.println(one+"   "+two);
                return (int) (two-one);
            }
        });
        daan = Arrays.copyOf(points,K);
//        for (int i=0;i<K;i++)
//            daan[i] = points[i];
//        }
        return daan;
    }

    public int[][] kClosest2(int[][] points, int K) {
        if (points == null || points.length == 0) return new int[0][];
        if (K >= points.length) return points;
        int left = 0, right = points.length - 1, pos = -1;
        while (pos != K - 1) {
            //牛，快排，如果快排的当前元素被放在k-1的位置上时，说明当前快排的左边就是需要的全部结果，即使有可能无序，但是满足结果
            pos = partition(points, left, right);
            if (pos < K - 1) left = pos + 1;
            if (pos > K - 1) right = pos - 1;
        }
        return Arrays.copyOf(points, K);
    }

    public int partition (int[][] points, int left, int right) {
        int[] tmp = points[left];
        int dis = points[left][0] * points[left][0] + points[left][1] * points[left][1];
        while (left < right) {
            while (left < right && (points[right][0] * points[right][0] + points[right][1] * points[right][1]) >= dis) right--;
            if(left < right) swap(points, left, right);
            while (left < right && (points[left][0] * points[left][0] + points[left][1] * points[left][1]) <= dis) left++;
            if(left < right) swap(points, left, right);
        }
        swap(points, left, right);
        return left;
    }

    public void swap(int[][] points, int left, int right) {
        int[] tmp = points[left];
        points[left] = points[right];
        points[right] = tmp;
    }
}
